// 核心：前缀树以及dfs算法
    class TrieNode {
        constructor(value) {
            this.END = false;
            this.children = {};
            this.value = value;
          }
    }
    let root = null;
    var arrList = [];
    function Trie() {
        root =  new TrieNode();
    };
    Trie.prototype.insert =  function(word) {
        let currentNode = root;
        for(let i = 0; i < word.length; i++) {
            if(currentNode.children[word[i]] == undefined) {
                currentNode.children[word[i]] = new TrieNode();
            }
            currentNode = currentNode.children[word[i]];
        }
        currentNode.END = true;
    };
    let searchPrefix = (word) => {
        let currentNode = root;
        for(let i = 0; i < word.length; i++) {
            if(currentNode.children[word[i]]) {
                currentNode = currentNode.children[word[i]];
            } else {
                return null;
            }
        }
        return currentNode;
    }

    let dfs = (currentNode, curStr='', res=[]) => {
        if(currentNode.END == false) {
            let children = currentNode.children;
            for (const child in children) {
                curStr = curStr+child;
                currentNode = currentNode.children[child]
                dfs(currentNode,curStr,res);
            }
        } else {
            res.push(curStr);
        }
        return res;
    }
    Trie.prototype.search = function(word) {
        let currentNode =searchPrefix(word);
        return currentNode != null && currentNode.END;
    };
    Trie.prototype.startsWith = function(prefix) {
        return searchPrefix(prefix) != null ? dfs(searchPrefix(prefix) ) : [];
    }
    export {Trie}


